1. Field of the Invention
The present invention relates to digital video image coding, and, in particular, to motion estimation for encoding video image data and to motion compensation for decoding encoded video image data.
2. Description of the Related Art
In order to transmit video images over narrow bandwidth channels and/or store video images efficiently, digital video data is preferably coded using known methods of compression. For example, to display real-time motion video on personal computer (PC) systems having limited available memory and processing time, the digital image data is preferably encoded utilizing as much of the redundancy in sequences of image frames as possible. For example, successive images in a sequence are visually similar. One way to take advantage of this redundancy is to encode video images using motion estimation and motion compensation. In motion estimation, an image encoder generates motion vectors that indicate the relative movements of different regions from one image frame to form an approximation to various regions in the next image frame.
Video images that are encoded using motion estimation are decoded using motion compensation. In motion compensation, an image decoder approximates an image frame by moving different regions of the previous image frame according to the motion vectors generated by an encoder during motion estimation.
In conventional motion estimation, an image frame n is divided into rectangular or square subimages called blocks. Each block of image frame n is then compared to the previous image frame n-1 to attempt to identify a region in the previous image frame n-1 that corresponds to that block of image frame n. A motion vector is then generated for each block of image frame n that has an identified corresponding region in image frame n-1. The motion vector indicates the relative vector distance between the block of image frame n and the corresponding region of image frame n-1.
The encoded image may be subsequently decoded using motion compensation in which the motion vectors indicate the regions of the previous image frame n-1 that are to be used to estimate blocks of the current image frame n. These estimated blocks may then be adjusted using additional correction data. Such additional correction data may be generated, for example, during encoding by taking the difference between each block of image frame n and each corresponding region of image frame n-1.
Referring now to FIG. 1, there are depicted graphical representations of two consecutive (16.times.16) pel images 100 and 200 in a video image sequence generated by a camera slowly panning from left to right across a fixed scene at a constant rate of two pels per frame. The letters A through Z are used in FIG. 1 to represent different pel values.
As the camera pans to the right, the image appears to shift to the left within the image boundaries. Thus, the data in columns 2 through 15 of image 100 are identical to the data in columns 0 through 13 of image 200. The data in columns 14 and 15 of image 200 correspond to a part of the scene that was outside of image 100. Note that, for the limited purposes of this description, Fig. 1 does not depict all the pel data of images 100 and 200.
According to conventional motion estimation, image 200 may be divided into sixteen (4.times.4) subimages or blocks. The encoder then compares each individual block of image 200 to image 100 to attempt to identify the region of image 100 that most closely matches that block of image 200. For example, the encoder may select region 102 of image 100 (corresponding to rows 8 through 11 and columns 6 through 9) as most closely matching block 202 of image 200 (corresponding to rows 8 through 11 and columns 4 through 7). The encoder then generates a motion vector for block 202 that corresponds to the relative vector distance between region 102 and block 202.
The decoder may subsequently perform motion compensation to estimate (and, in this particular example, to reproduce exactly) block 202 of image 200 using only the data of image and the motion vector for block 202. The motion vector for block 202 instructs the decoder to shift the data from region 102 of image 100 to estimate block 202 of image 200. Thus, instead of representing block 202 by sixteen distinct pel values, block 202 may be more efficiently represented, in this example, by a single motion vector.
One rule of conventional motion estimation/compensation is that the encoder cannot instruct the decoder to move image data from outside the allowable area. For example, referring again to FIG. 1, conventional motion compensation cannot be used to estimate block 204 of image 200 (corresponding to rows 4 through 7 and columns 12 through 15). This is because part of the data in block 204 of image 200 was outside of previous image 100. Under the conventional rules of motion estimation/compensation, block 204 must be reconstructed using means other than motion compensation, such as by transmitting a reference or intra-coded block. A reference or intra-coded block is a block that is encoded without reference to any previous image frame.
As a result of this rule of conventional motion estimation/compensation, each region of a previous image frame n-1 that is identified as matching a block of current image frame n must be the same size as that block and must be contained entirely within the allowable area of previous image frame n-1.
In conventional non-real-time motion estimation/compensation applications, the allowable area over which motion compensation may be performed is limited only by the edges of the overall image. Motion vectors may be as large as necessary so long as the block in the current image frame n and the corresponding region in the previous image frame n1 both lie within the respective pel images and provided the coding scheme can accommodate such vectors. There are problems, however, with using conventional motion estimation/compensation to display real-time motion video on systems such as PC systems or other data players.
For example, if the entire image frame is defined as the allowable area, then the processing time required to perform motion estimation may exceed the requirements for real-time motion video. In general, the larger the area over which motion estimation is permitted to be performed, the greater the processing time required.
In addition, in systems such as PC systems, the image data for a given image frame may be stored in different sectors of a memory chip. If the allowable area is the entire image frame, motion compensation may require access to image data that crosses sector boundaries of the memory chip. Such access adds to the processing time and decoding based on such motion compensation may not meet the processing time requirements for real-time motion video.
It is accordingly an object of this invention to overcome the disadvantages and drawbacks of the prior art and to provide methods and apparatuses for performing motion estimation and motion compensation for displaying real-time motion video on conventional systems such as PC systems or other data players.
It is a further object of this invention to perform motion estimation and motion compensation under the hardware and software limitations imposed by video systems.
Further objects and advantages of this invention will become apparent from the detailed description of a preferred embodiment which follows.